#include <algorithm>
#include <chrono>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>

template <typename T>
T partition(T first, T last)
{
	auto pivot = *(--last);
	auto temp = first;

	while (first < last)
	{
		if (*first < pivot)
		{
			std::swap(*first, *temp);
			++temp;
		}
		++first;
	}
	std::swap(*temp, pivot);

	return temp;
}

template <typename T>
void quick_sort(T first, T last)
{
	if (first < last)
	{
		auto pivot = partition(first, last);
		quick_sort(first, pivot);
		quick_sort(std::next(pivot), last);
	}
}


const int kSize = 1000;        // Size of vector to sort
const int kRangeFrom = -100000;  // Start of range for random number generator
const int kRangeTo = 100000;     // End of range for random number generator

int main()
{
	std::random_device rd;
	std::mt19937 mt(rd());
	std::uniform_int_distribution<int> dist(kRangeFrom, kRangeTo);

	std::vector<int> v(kSize);
	std::generate(v.begin(), v.end(), [&](){ return dist(mt); });

	auto start = std::chrono::steady_clock::now();
	quick_sort(v.begin(), v.end());
	auto end = std::chrono::steady_clock::now();

	std::cout << "Is Sorted: " << std::is_sorted(v.begin(), v.end()) << std::endl;
	std::cout << "Completed in: " << std::chrono::duration<double, std::milli>(end - start).count() << " ms" << std::endl;

	return 0;
}